package arithmetic2;

/**
 * Created by AJie on 2019/7/23
 * Function :
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 *
 * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 *
 * 你可以假设 nums1 和 nums2 不会同时为空。
 *
 * 示例 1:
 *
 * nums1 = [1, 3]
 * nums2 = [2]
 *
 * 则中位数是 2.0
 * 示例 2:
 *
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 *
 * 则中位数是 (2 + 3)/2 = 2.5
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu-b/
 */
public class T_004_MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        System.out.println(5/3);
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] A =nums1,B=nums2;
        int m = A.length;
        int n = B.length;
        if (m > n) { // to ensure m<=n
            int[] temp = A; A = B; B = temp;
            int tmp = m; m = n; n = tmp;
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;//关键点1，一半的数量（或者最中间的个数），左边的个数。
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;// m左边的个数
            int j = halfLen - i;//n 左边的个数，关键点 2，i  j 关系
            if (i < iMax && B[j-1] > A[i]){
                iMin = i + 1; // i is too small
            }
            else if (i > iMin && A[i-1] > B[j]) {
                iMax = i - 1; // i is too big
            }
            else { // i is perfect
                int maxLeft = 0;
                if (i == 0) { maxLeft = B[j-1]; }// 对应的i==imin
                else if (j == 0) { maxLeft = A[i-1]; }//对应i==imax
                else { maxLeft = Math.max(A[i-1], B[j-1]); }
                if (((m + n) & 1) == 1 ) { return maxLeft; }//m+n 奇数

                //m+n 偶数
                int minRight = 0;
                if (i == m) { minRight = B[j]; }//m<=n 所以右边都是 B
                else if (j == n) { minRight = A[i]; }//  右边都是m
                else { minRight = Math.min(B[j], A[i]); }

                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }
}
